import java.util.function.BiFunction;

public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        test(MedianOfTwoSortedArrays::linearSolution);
        test(MedianOfTwoSortedArrays::logSolution);
    }

    static void test(BiFunction<int[], int[], Double> f) {
        System.out.println();

        double r = f.apply(new int[] { 1, 3 }, new int[] { 2 });
        System.out.println(r);  // 2.000000

        r = f.apply(new int[] { 1, 2 }, new int[] { 3, 4 });
        System.out.println(r);  // 2.500000
    }

    // 线性算法 O(m+n)
    static double linearSolution(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int i = 0;
        int j = 0;
        int mid = (m + n) / 2;
        int left = 0;
        int right = 0;

        // i和j不要看作索引，而是看作越过元素的个数
        // 假设m+n=4, 则mid=2, 中位数是第2和第3个元素的一半
        // 跳出循环条件为i+j=3,代表越过3个，right刚好记录第3个元素，left则记录第2个元素
        // 假设m+n=5, 则mid=2, 中尉书是第3个元素，根据上行描述,right是答案
        while (i + j <= mid) {
            left = right;
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    right = nums1[i];
                    i++;
                } else {
                    right = nums2[j];
                    j++;
                }
            } else if (i < m) {
                right = nums1[i];
                i++;
            } else {
                right = nums2[j];
                j++;
            }
        }

        if ((m + n) % 2 == 0) {
            return (left + right) / 2.0;
        } else {
            return right;
        }
    }

    /**
     * 二分算法 O(log(m+n))
     * 通过二分查找的方式，找到合适的分割点，使得分割点左侧的最大值小于等于右侧的最小值
     */
    static double logSolution(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return logSolution(nums2, nums1);
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0;
        int high = x;

        while (low <= high) {
            // x分割点二分查找
            int partitionX = (low + high) / 2;

            // y分割点由x分割点动态决定，使得
            // partitionX + partitionY = (x + y + 1) / 2,
            int partitionY = (x + y + 1) / 2 - partitionX;

            int xPLeft = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int xPRight = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

            int yPLeft = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int yPRight = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            // [xPLeft, xPRight]可以处于[yPLeft, yPRight]中间,包括边界上
            if (xPLeft <= yPRight && xPRight >= yPLeft) {
                if ((x + y) % 2 == 0) {
                    return (Math.max(xPLeft, yPLeft) + Math.min(xPRight, yPRight)) / 2.0;
                } else {
                    return Math.max(xPLeft, yPLeft);
                }
            }
            // [xPLeft, xPRight]在[yPLeft, yPRight]的右侧
            else if (xPLeft > yPRight) {
                high = partitionX - 1;
            }
            // 不在中间也不在右侧，则
            // [xPLeft, xPRight]在[yPLeft, yPRight]的左侧
            else {
                low = partitionX + 1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }
}
